NetworkX comes with a large number of builtin graph generators. These can be especially useful for testing out new measures, metrics, and dynamics, on already well tested algorithms. In this notebook, we'll go through some of the different classes of graph generators included in NetworkX and write a few of our own. There are a lot of generators in NetworkX so before you implement your own check to see NetworkX already has it!
In [ ]:
import networkx as nx
NetworkX has the ability to make a bunch of the graphs we made in the previous section. They mainly fall under the classic namespace. For example, to make a complete graph, we could just use:
In [ ]:
C = nx.generators.classic.complete_graph(5)
C.edges()
We don't actually have to use the full namespace call that is nx.generators.classic.complete_graph, everythin is under the nx module
In [ ]:
C = nx.complete_graph(5)
Explore the classic generators, create graphs for at least 3 of them. You can list the graphs by typing nx.generators.classic.[TAB]. Read the documentation for each (remember you can type (nx.circulant_graph?) to see the documentation
In [ ]:
NetworkX contains a number of small graphs from classic work. For example the Zachary karate Club is often used for testing community finding algorithms. It is included in networkx along with the community information
In [ ]:
KC = nx.karate_club_graph()
In [ ]:
KC.nodes(data=True)
Others are included under nx.generators.social. Explore the davis_southern_women_graph, what is special about it?
In [ ]:
DSW = nx.davis_southern_women_graph()
DSW.nodes()
Random graphs are often used as models for various physical phenomena, and testing new measures and dynamics. NetworkX has a bunch of them built in. For example the classic Erdős–Rényi graph is implemented as gnp_random_graph which takes a number of nodes and a probability of connection between any two nodes
In [ ]:
ER = nx.gnp_random_graph(100,1.0/100)
In [ ]:
ER.size()
A slight variant allows you to give it the total number of edges to be placed randomly
In [ ]:
ER2 =nx.gnm_random_graph(100,50)
In [ ]:
ER2.size()
The Erdős–Rényi does not have many of the properties seen in real world social network data, particularly, triadic closures. Watts and Strogatz developed a random graph model which accounts for this, and it's implemented in NetworkX!
In [ ]:
WS = nx.watts_strogatz_graph(10,4,.2)
In [ ]:
WS.edges()
A common feature of complex networks is their heavy-tailed degree distribution. That is the degrees of the nodes in a graph varies over many orders of magnitude. NetworkX contains a number of random graph models that have power law degree sequences. One of the most famous is the Barabási–Albert model. In this model nodes are added sequentially and a fixed number of edges between new nodes and existing nodes are added with nodes being selected with probability proportional to their degree.
In [ ]:
BA = nx.barabasi_albert_graph(10000,1)
In [ ]:
deg = BA.degree().values()
(min(deg),max(deg))
We'll plot degree sequences in the next lesson on graph analysis.
One more exercise and then we'll get to the fun stuff. On disadvantage of the original Barabási–Albert model is that it had an integer average degree and the degree distribution was power law, but could only have integer exponent. Let's make a model that is able to ahve non-integer exponent.
Let's write a new model. Instead of adding a fixed number of edges with each node, we add a random number of edges from a Poisson distribution with mean $\lambda$. To ensure the graph stays connected, if the random number of edges is 0 we add at least 1 edge. Just as in the original model, we connect to new nodes to the graph to nodes proportional to the degree of the node.
First lets find a function that can generate poisson random numbers for us. It's easy to do with the numpy package, we can import numpy and then just call np.random.poisson to generate a random number with $Poisson(\lambda)$
In [ ]:
import numpy as np
In [ ]:
np.random.poisson(3.2)
A trick to write a fast BA implementation is to maintain a list of nodes with nodes repeated in the list each time they have a connection made.
In [ ]:
def poisson_BA(n,l):
start = max(2,np.random.poisson(l)) # start with at least two nodes
G = nx.complete_graph(start)
#an easy list to grab nodes from
repeated_nodes = []
# For each node at it's label to the list for as many times as it's degree
u = start
while u < n:
# Using the the poisson random number generator, generate a number of connections
# Make Sure it's greater than 1
# Store that variable in `connections`
for _ in range(connections):
# For as many connections as it has select a node at random from repeated_nodes
# Hint numpy as a np.random.choice function
# Be sure to update repeated_nodes!
u += 1
return G
In [ ]:
G = poisson_BA(1000,np.pi)
In [ ]:
deg = G.degree().values()
min(deg),max(deg)
In [ ]:
np.mean(G.degree().values())